Computer graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices. Graphical user interfaces have replaced textual interfaces as the standard means for user computer interaction.
Graphics have also become a key technology for communicating ideas, data, and trends in most areas of commerce, science, and education. Until recently, real time user interaction with three dimensional (3D) models and pseudo-realistic images was feasible on only very high performance workstations. These workstations contain dedicated, special purpose graphics hardware, and are typically very expensive. The spectacular progress of semiconductor fabrication technology has made it possible to do the same real time 3D animation, with color shaded images of complex objects, described by thousands of polygons, on rendering subsystems of only a few chips. The most recent and most powerful workstations are capable of rendering completely life-like, realistically lighted, 3D scenes.
In a 3D computer generated image, objects are typically described by data models. These models store descriptions of "primitives" (usually mathematically described polygons and polyhedra) that define the shape of the object, the object attributes, and the connectivity and positioning data describing how the objects fit together. The component polygons and polyhedra connect at common edges defined in terms of common vertices and enclosed volumes. The polygons are textured, Z-buffered, and shaded/illustrated onto an array of pixels, creating a realistic 3D image.
Many applications require the generation of smooth surfaces and smooth curves. To realistically generate a real-world image, the surfaces of objects in the image need to be realistically modeled. The most common representation for 3D surfaces are "polygon meshes." A polygon mesh is a set of connected, polygonally bounded, planar surfaces. Open boxes, cabinets, and building exteriors can be easily and naturally represented by polygon meshes. Polygon meshes, however, are less easily used to represent objects with curved surfaces.
Referring now to prior art FIG. 1A, a simple polygon mesh of a section 10 of a cone is shown, while prior art FIG. 1B shows an actual section 11 of a cone. Each polygon of the section 10 is a mathematical representation of a corresponding portion of the surface of the section 11. The interconnecting vertices (e.g., vertices 13) and the interconnecting edges of the polygons (e.g., edges 12) collectively define the surface of section 10 in 3D space. There are obvious short comings, however, in the accuracy of the section 10 in comparison to actual section 11. The polygons model the surface of section 11, but the representation is only approximate. The "errors" of the approximation can be made arbitrarily small by using more and more polygons to create an increasingly accurate piece wise linear approximation.
Referring now to prior art FIG. 2A, prior art FIG. 2B, and prior art FIG. 2C, an initial representation 21, an intermediate representation 22, and a final representation 23, are shown respectively. The initial representation 21 is a polygon mesh of a rain drop. As described above, initial representation 21 consists of a fewer number of polygons, leading to a "blocky," or geometrically aliased, representation of the rain drop. It should be noted that the polygons of initial representation 21 are comprised of triangles, whereas the polygons of section 10 are comprised of quadrilaterals. Regardless of the nature of the polygon primitive (triangle, quadrilateral, and the like) used to model a curved surface, the general properties, e.g., geometric aliasing, are substantially the same.
In proceeding from initial representation 21 to intermediate representation 22, the number of polygons in the polygon mesh of initial representation 21 are increased. Computer graphics engineers rely upon a technique known as surface subdivision to provide a straight forward method of increasing the number of polygons comprising a polygon mesh. In the subdivision technique, the polygons comprising the polygon mesh are each divided into a plurality of "daughter" polygons. The daughter polygons share most of the characteristics of the "parent" polygon, however, their position and orientation in 3D space is influenced by the position and orientation of neighboring daughter polygons. The nature and degree of this influence is implementation specific, i.e., particular algorithms cause differing effects. Subdivision algorithms determine the placement of the vertices and edges of the daughter polygons. In so doing, an exemplary subdivision algorithm utilizes not only information regarding the parent polygon, but also information regarding the connectivity of the parent polygon with its neighboring polygons. The subdivision algorithm places and connects the daughter polygons in 3D space such that the polygon mesh becomes a smoother, less geometrically aliased representation of the real life object being modeled. Thus, intermediate representation 22 is derived from initial representation 21 through subdivision processing, and after several iterations, final representation 23 is derived. It should be noted that although final representation 23 appears as a smooth, realistic, rain drop, final representation 23 is still a polygon mesh comprised of a large number of polygons in the same manner as initial representation 21. The much larger number of polygons in final representation 23 contribute to the smoother, more realistic appearance.
The subdivision algorithms described above are essentially a set of geometry based rules. A computer system implements these rules in the process of computing polygon subdivision, using the rules to manipulate the polygons of the mesh. A complex model can include many hundreds of thousands of polygons. In performing surface subdivision processing, the computer system needs to perform geometric manipulations on each of the polygons comprising the mesh, which can lead to severe computational loads. These computational loads often slow the graphics processing speed of the computer system.
In addition to the computational loads, the computer system has a finite amount of memory space. Each polygon in the mesh has a number of attributes which need to be stored, e.g., the coordinates of each of the vertices of the polygon, the connective relationship of the polygon in relation to its neighbors, the orientation of the polygon in 3D space, and the like. Thus, all though it is desirable to model an object with a large number of polygons in order to reduce geometric aliasing, increasing the number of polygons quickly consumes the memory resources of the computer system. Surface subdivision processing may provide a straight forward method of increasing the realism of a modeled object, but it also reduces the number of objects a computer system can simultaneously store and manipulate, surface subdivision processing geometrically increases the number of polygons in a modeled object. The lack of memory resources is thus, a limiting factor in the graphics process.
Typical prior art methods of storing polygons in memory grow increasingly cumbersome as the size (number of polygons) of the polygon mesh increases. Information regarding the coordinates of each of the vertices of the polygons, the connective relationship of the polygon in relation to its neighbors, and the like, are stored in data structures the computer system maintains in memory. Several pointers and indexing tables are required in order to access information regarding particular polygons and to subsequently access information about neighboring polygons. This slows the memory accessing process by requiring extra steps to index the particular polygons.
The large memory space occupied by a complex polygon mesh can also lead to a serialized, non-parallel graphics computation processing. The large polygon mesh typically fits only in a large data structure maintained in the computer system's main memory. Thus, even though the computer system may have a number of graphics co-processors, the large data structure is not easily adapted to parallel, hardware based acceleration. Most of the processing is handled by the CPU.
Thus, what is desired is a system for efficiently implementing surface subdivision in a polygon mesh. The system should be able to efficiently subdivide a curved surface using a minimum amount of memory. What is further desired is system for efficiently storing a complex polygon mesh. The system should store polygon attributes, e.g., the coordinates of each of the vertices of the polygon, the connective relationship of the polygon in relation to its neighbors, the orientation of the polygon in 3D space, and the like, in an easily indexed, easily accessed, data structure in memory. What is further desired is a surface subdivision system which lends itself to parallel computation in order to increase the speed of the 3D graphics process. The system of the present invention satisfies the above requirements.